const TreeNode = require('../chapter-7/binary_tree_chain')

// 可以利用插入算法创建 二叉排序树

/**
 * 为配合插入节点算法而改良的查找算法
 * 查找成功返回 1，并返回对应节点
 * 失败返回 0，并返回最后一个查找的节点，用于插入
 * @param {*} bt 
 * @param {*} key 
 * @param {*} q bt的双亲节点
 */
function searchBST(bt, key, q) {
    if (!bt) return { code: 0, node: q}
    if (bt.data === key) return {code: 1, node: bt}
    if (key < bt.data) {
        return searchBST(bt.leftChild, key, bt)
    } else {
        return searchBST(bt.rightChild, key, bt)
    }
}


/**
 * 插入节点
 * 插入成功 1
 * 插入失败 0
 * @param {*} bt 需要插入的二叉树
 * @param {*} key 需要插入的值
 */
function insertBST(bt, key) {
    let res = searchBST(bt, key, null)
    if(res.code === 0) {
        const n = new TreeNode()
        n.data = key
        if (!res.node) { // 如果是空树
            bt = n
        } else if (key < res.node.data) {
            res.node.leftChild = n
        } else {
            res.node.rightChild = n
        }
        return bt
    } else {
        return 0
    }
}

let t = null
const x = [63, 90, 70, 55, 67, 42, 98, 83, 10, 45, 58]
for (let item of x) {
   t = insertBST(t, item)
}
console.log(t)